﻿#define _CRT_SECURE_NO_WARNINGS 1
//给定一个整数数组 nums 和一个整数目标值 target，
//请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
//你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
//你可以按任意顺序返回答案。

//输入：nums = [2, 7, 11, 15], target = 9
//输出：[0, 1]
//解释：因为 nums[0] + nums[1] == 9 ，返回[0, 1]
//[3,2,4] 6  
// [1,2]
//[3,3] 6
//[0,1]

#include<stdio.h>
#include<stdlib.h>

int cmp(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
//暴力求解
//2 7 11 15
int HalfSearch(int* nums, int begin,int n, int  aim_num)
{
	int left = begin;
	// int right = n-1;
	int right = 0;
	if (begin != n)
		right = n - 1;
	else//只有一个数的情况
		right = n;
	//如果数据是重复的话，返回下标相同，需要考虑进来

	while (left <= right)//如果查找的数刚好在这呢？所以要等于
	{
		int mid = (left + right) / 2;
		//2 4 4   8
		if (nums[mid] > aim_num)
			right = mid - 1;
		else if (nums[mid] < aim_num)
			left = mid + 1;
		else
		{
			//特殊考虑---重复，因为是向0取整的所以+1不用考虑-1
			//或者跳过这个重复的呀。
			// 1 2 3  3 6 8
	
			// 1 2 3 4
			//if (nums[mid + 1] == nums[mid])
			//	return mid + 1;
			//else

				return mid;
		}
	}
	return -1;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
	*returnSize = 2;
	//要返回下标、排序后原来的下标变化
	//考虑建立以元素和下标关系。
	int i = 0;
	int n = 0;
	int* arr= (int*)malloc(sizeof(int) * numsSize);
	for (i = 0; i < numsSize; i++)
	{
		arr[i] = nums[i];
	}
	qsort(arr, numsSize, sizeof(int), cmp);//排序 原来的顺序变了。
	
	int* tar_nums = (int*)malloc(sizeof(int) * 2);
	if (NULL == tar_nums)
	{
		perror("");
		exit(0);
	}
	//先找到最适下标， 没有最适下标如何？
	
	//如果是负数的情况就会有问题！
	//for (i = 0; i < numsSize; i++)
	//{
	//	if (arr[i] > target)
	//	{
	//		n = i;
	//		break;
	//	}
	//}
	//if (i == numsSize)
	//	n = i;
	//找数字

	int ret = 0;
	for (i = 0; i < /*n*/ numsSize; i++)
	{
		//二分查找
		int aim_num = target - arr[i];
		//ret = HalfSearch(arr, i,n ,aim_num);
		//ret = HalfSearch(arr, i+1, n, aim_num);
		ret = HalfSearch(arr, i + 1, numsSize, aim_num);//接收返回的下标值


		if ( ret != -1)//返回找到的下标
		//设置为0不妥，虽然也没错。来个最不可能的值，才更好
			break;
	}
	//找对应的坐标
	int flag = 1;
	int flag = 0;
	int flag1 = 1;
	for (int j  = 0; j < numsSize; j++)
	{
		if (arr[i] == nums[j] && flag /*&& flag != 1*/ )
		{
			tar_nums[0] = j;
			flag = 0;
			//flag++;
		}
		else if (arr[ret] == nums[j] && flag1 /*&& flag != 2*/)
		{
			tar_nums[1] = j;
			flag1 = 0;
			//flag++;

		}
	}
	return tar_nums;
}


int main()
{
	int nums[] = { -1,-2,-3,-4,-5,- 8 };
	int sz = sizeof(nums) / sizeof(nums[0]);
	int target = -8;
	int returnSize = 0;
	int* arr = twoSum(nums, sz, target, &returnSize);
	for (int i = 0; i < returnSize; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}